import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * 1277.统计全为1的正方形子矩阵
 * 给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
 */
public class CountSquares {


    @Test
    public void test1() {
        Assertions.assertEquals(15, countSquares(new int[][]{
                {0, 1, 1, 1},
                {1, 1, 1, 1},
                {0, 1, 1, 1}
        }));
    }

    @Test
    public void test2() {
        Assertions.assertEquals(7, countSquares(new int[][]{

                {1, 0, 1},
                {1, 1, 0},
                {1, 1, 0}
        }));
    }


    public int countSquares(int[][] matrix) {


        int count = 0;

        for (int i : matrix[0]) {
            count += i;
        }


        for (int i = 1; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {


                if (matrix[i][j] == 1) {
                    count++;
                    for (int previousColumn = j - 1, previousRow = i - 1; previousColumn >= 0 && previousRow >= 0; previousColumn--, previousRow--) {
                        if (matrix[i][previousColumn] == 0) {
                            break;
                        }
                        if (matrix[previousRow][j] == 1) {

                            boolean isZero = false;
                            for (int x = previousRow; x < i; x++) {
                                for (int y = previousColumn; y < j; y++) {

                                    if (matrix[x][y] == 0) {
                                        isZero = true;
                                        break;
                                    }
                                }
                            }
                            if (!isZero) {
                                count++;
                                continue;
                            }

                        }
                        break;

                    }
                }

            }
        }

        return count;
    }
}
